#!/usr/bin/env python
# encoding: utf-8

# @Author  : vfengcc
# @File    : knapsack.py
# @Time    : 2020/1/12 22:26

def main():
    '''
    本周作业内容如下：
    假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。
    名称	价格（美元）	重量（kg）
    电脑	    200	        20
    收音机	20	        4
    钟	    175	        10
    花瓶	    50	        2
    书	    10	        1
    油画	    90	        9
    '''
    goods = [
        ('电脑', 200, 20),
        ('收音机', 20, 4),
        ('钟', 175, 10),
        ('花瓶', 50, 2),
        ('书', 10, 1),
        ('油画', 90, 9),
    ]

    # 计算价格/重量 比重 生成新列表
    goodsNew = list(map(lambda t: (*t, t[1] / t[2]), goods))
    # print(goodsNew)
    # ls1 = sorted(goodsNew,key=lambda t: t[1])
    # print('按照价格排序',ls1)
    # ls2 = sorted(goodsNew,key=lambda t: t[2])
    # print('按照重量排序',ls2)
    ls3 = sorted(goodsNew, key=lambda t: t[3], reverse=True)
    print('按照价格/重量 比值排序', ls3)

    ableWeight = 20         # 可放入的物品总重量
    pickedsPW = [0, 0]      # 放入书包物品的价格和重量
    pickeds = ''            # 放入书包物品信息
    nopickeds = ''          # 未放入书包物品信息
    i = 0
    for item in ls3:
        if ableWeight > item[2]:    # 可用放入背包
            ableWeight -= item[2]
            pickedsPW[0] += item[1]
            pickedsPW[1] += item[2]
            pickeds += '\t[{}]，价值{}，重量{}'.format(*item) + '\n'
        else:
            nopickeds += '\t[{}]，价值{}，重量{}'.format(*item) + '\n'

    print('拿走：')
    print(pickeds)
    print('\t【物品总价值{},总重量{}】'.format(pickedsPW[0], pickedsPW[1]))
    print('留下:')
    print(nopickeds)

if __name__ == '__main__':
    main()


